package algorithm;

/**
 * @author apple
 * Recursion 递归算法
 **/
public class Recursion {

    /**
     * 生成斐波拉切数列  fabonacci
     **/
    public static int f(int n) {
        Integer[] arr = new Integer[n + 1];
        if (n <= 1) {
            return n;
        }
        /**判断是否计算过**/
        if (arr[n] != null) {
            /**已经计算过**/
            return arr[n];
        } else {
            /**未计算过**/
            arr[n] = f(n - 1) + f(n - 2);
            return arr[n];
        }
    }

    /**
     * 阶乘 递归
     **/
    public static int nTimes(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * nTimes(n - 1);
    }

    /**
     * 小青蛙跳楼梯
     **/
    public static int frogJump(int n) {
        if (n <= 2) {
            return n;
        }
        return frogJump(n - 1) + frogJump(n - 2);
    }

    public static void main(String[] args) {
        /**生成斐波拉切数列 根据参数值，计算指定第n个数的斐波拉切数列的值 f(10) =55 第10个数为55**/
        int count =10;
        for (int i = 1; i <= count; i++) {
            System.out.println(i + "=" + f(i));
        }
        /**计算阶乘数**/
        System.out.println("阶乘");
        for (int i = 1; i < count; i++) {
            System.out.println(i + "！=" + nTimes(i));
        }
        /**小青蛙跳楼梯**/
        System.out.println("小青蛙跳楼梯");
        for (int i = 2; i < count; i ++) {
            System.out.println(i + "台阶有" + frogJump(i)+"种跳法");
        }
    }

}
